\section{C99 restrict}
\myindex{\CLanguageElements!C99!restrict}
\myindex{Фортран}

А вот причина, из-за которой программы на Фортран, в некоторых случаях, работают быстрее чем на Си.

\begin{lstlisting}[style=customc]
void f1 (int* x, int* y, int* sum, int* product, int* sum_product, int* update_me, size_t s)
{
	for (int i=0; i<s; i++)
	{
		sum[i]=x[i]+y[i];
		product[i]=x[i]*y[i];
		update_me[i]=i*123; // some dummy value
		sum_product[i]=sum[i]+product[i];	
	};
};
\end{lstlisting}

Это очень простой пример, в котором есть одна особенность: 
указатель на массив \TT{update\_me} может быть указателем на массив
\TT{sum}, \TT{product}, или даже 
\TT{sum\_product}---ведь нет ничего криминального в том 
чтобы аргументам функции быть такими, верно?

Компилятор знает об этом, поэтому генерирует код, где в теле цикла будет 4 основных стадии:

\begin{itemize}
\item вычислить следующий \TT{sum[i]}
\item вычислить следующий \TT{product[i]}
\item вычислить следующий \TT{update\_me[i]}
\item вычислить следующий \TT{sum\_product[i]}---на этой стадии придется снова загружать из памяти подсчитанные
 \TT{sum[i]} и \TT{product[i]}
\end{itemize}

Возможно ли соптимизировать последнюю стадию?
Ведь подсчитанные \TT{sum[i]} и \TT{product[i]} 
не обязательно снова загружать из памяти, ведь мы их только что подсчитали.

Можно, но компилятор не уверен, что на третьей стадии ничего не затерлось!

Это называется
\q{pointer aliasing}, ситуация, когда компилятор не может быть уверен, что память на которую указывает 
какой-то указатель, не изменилась.

\IT{restrict} в стандарте Си C99 \InSqBrackets{\CNineNineStd{} 6.7.3/1}
это обещание, данное компилятору программистом, что аргументы функции, отмеченные этим ключевым словом,
всегда будут указывать на разные места в памяти и пересекаться не будут.

Если быть более точным, и описывать это формально, \IT{restrict} показывает, что только данный указатель будет
использоваться для доступа к этому объекту, больше никакой указатель для
этого использоваться не будет.

Можно даже сказать, что к всякому объекту, доступ будет осуществляться только через
один единственный указатель, если он отмечен как \IT{restrict}.

Добавим это ключевое слово к каждому аргументу-указателю:

\begin{lstlisting}[style=customc]
void f2 (int* restrict x, int* restrict y, int* restrict sum, int* restrict product, int* restrict sum_product, 
	int* restrict update_me, size_t s)
{
	for (int i=0; i<s; i++)
	{
		sum[i]=x[i]+y[i];
		product[i]=x[i]*y[i];
		update_me[i]=i*123; // some dummy value
		sum_product[i]=sum[i]+product[i];	
	};
};
\end{lstlisting}

Посмотрим результаты:

\lstinputlisting[caption=GCC x64: f1(),style=customasmx86]{\CURPATH/f1_RU.asm}

\lstinputlisting[caption=GCC x64: f2(),style=customasmx86]{\CURPATH/f2_RU.asm}

Разница между скомпилированной функцией \TT{f1()} и \TT{f2()} такая:
в \TT{f1()}, \TT{sum[i]} и \TT{product[i]} загружаются снова посреди тела цикла,
а в \TT{f2()} этого нет, используются уже подсчитанные значения, 
ведь мы \q{пообещали} компилятору, 
что никто и ничто не изменит значения в \TT{sum[i]} 
и \TT{product[i]} во время исполнения тела цикла, 
поэтому он \q{уверен}, что значения из памяти можно не загружать снова.
Очевидно, второй вариант работает быстрее.

Но что будет если указатели в аргументах функций все же будут пересекаться?

Это на совести программиста, а результаты вычислений будут неверными.

Вернемся к Фортрану. 
Компиляторы с этого ЯП, по умолчанию, все указатели считают таковыми,
поэтому, когда не было возможности указать \IT{restrict} в Си, 
то компилятор с Фортрана в этих случаях мог генерировать более быстрый код.

Насколько это практично? 
Там, где функция работает с несколькими большими блоками в памяти.

Такого очень много в линейной алгебре, например.

Очень много линейной алгебры используется на суперкомпьютерах/\ac{HPC},
возможно, поэтому, традиционно, там часто используется Фортран, до сих пор
[Eugene Loh, \IT{The Ideal HPC Programming Language}, (2010)].
Ну а когда итераций цикла не очень много, конечно, 
тогда прирост скорости может и не быть ощутимым.

